import copy
import queue
import numpy as np

#表示从i到j两点之间的最近路径距离，i到j若无边则为最近路径上边的加和
inf = float("inf")
c_ij = [
    [inf,5,21,13,6,15,12,20],
    [5,inf,16,18,7,12,19,17],
    [21,16,inf,33,16,7,17,11],
    [13,18,33,inf,17,26,16,29],
    [6,7,16,17,inf,9,12,14],
    [15,12,7,26,9,inf,10,5],
    [18,19,17,16,12,10,inf,13],
    [20,17,11,29,14,5,13,inf]
]
N = len(c_ij)

class B_B_node:
    def __init__(self,commited:list,ban:list,reduced_cij,lowbound,row:list,column:list):
        self.commited = commited
        self.ban = ban
        self.cij = reduced_cij
        self.lowbound = lowbound
        self.n = len(reduced_cij)
        #两个list保存剩余的行和列序号
        self.row = row
        self.column = column

#约化函数，输入未约化矩阵，输出h的值和约化矩阵（每行列都至少有一个0）
def reduce(ccij):
    rou = []
    k = []

    cc_ij = copy.deepcopy(ccij)
    rou = np.min(cc_ij,axis = 1)
    #print("rou:",rou)
    for i in range(len(ccij)):
        for j in range(len(ccij)):
            cc_ij[i][j] -= rou[i]
    k = np.min(cc_ij,axis = 0)
    #print("k:",k)
    for i in range(len(ccij)):
        for j in range(len(ccij)):
            cc_ij[i][j] -= k[j]    
    return sum(rou)+sum(k),cc_ij

#定义函数用以删掉矩阵和row、column中的行和列
def dele(cij,row,column,edge):
    C = copy.deepcopy(cij)
    row1 = copy.deepcopy(row)
    column1 = copy.deepcopy(column)
    #删除行
    for i in range(len(row1)):
        if row1[i] == edge[0]:
            C = np.delete(C,i,axis=0)
            row1.remove(row1[i])
            break
    #删除列   
    for j in range(len(column1)):
        if column1[j] == edge[1]:
            C = np.delete(C,j,axis=1)
            column1.remove(column1[j])
            break
    return C,row1,column1

#定义函数用以将cij中ban掉的边设为inf
def ban(cij,row,column,edge): 
    C = copy.deepcopy(cij)           
    for i in range(len(row)):
        if row[i] == edge[0]:
            for j in range(len(column)):
                if column[j] == edge[1]:
                    C[i][j] = inf
                    continue
    return C

#定义函数用于消除子环
def del_sub(X_node:B_B_node,edge):
    start = edge[0]
    end = edge[1]
    i = 0
    while i < len(X_node.commited):
        if X_node.commited[i][1] == start:
            start = X_node.commited[i][0]
            i = 0
            continue
        elif X_node.commited[i][0] == end:
            end = X_node.commited[i][1]
            i = 0
            continue
        else:
            i += 1
    print("找到子环端点",[start,end])
    C = copy.deepcopy(X_node.cij)
    temp_row =copy.deepcopy(X_node.row) 
    temp_column = copy.deepcopy(X_node.column)
    for i in range(len(temp_row)):
        if temp_row[i] == end:
            for j in range(len(temp_column)):
                if temp_column[j] == start:
                    C[i][j] = inf
                    print("消除子环连接",[temp_row[i],temp_column[j]])
                    break    
    return C

def find_nextedge(X_node:B_B_node):#寻找下一个待处理边，返回theta值和边
    edges = []
    print(X_node.n)
    print("X下限:",X_node.lowbound)
    for k in range(X_node.n):
        for l in range(X_node.n):
            if X_node.cij[k][l] == 0:
                x_min = inf
                y_min = inf
                j = 0 
                i = 0
                while j < X_node.n :
                    if j == l:
                        j += 1
                        continue
                    if X_node.cij[k][j] <= x_min:
                        x_min = X_node.cij[k][j]
                    j += 1
                while i < X_node.n :
                    if i == k:
                        i += 1
                        continue
                    if X_node.cij[i][l] <= y_min:
                        y_min = X_node.cij[i][l]
                    i += 1
                edges.append([x_min + y_min,k,l])
    edges.sort(reverse=1)
    print(X_node.row,"\n",X_node.column)
    print(edges[0])
    return edges[0][0],[X_node.row[edges[0][1]],X_node.column[edges[0][2]]]


def build_left(X_node:B_B_node,theta,edge):#对当前X生成Y_
    node = copy.deepcopy(X_node)
    
    temp_row =copy.deepcopy(node.row) 
    temp_column = copy.deepcopy(node.column)
    node.ban.append(edge)
    node.cij = ban(node.cij,temp_row,temp_column,edge)
    
    Y_ = B_B_node(node.commited,node.ban,node.cij,node.lowbound + theta,node.row,node.column)

    print("Y_下限:",Y_.lowbound)
    return Y_

def built_right(X_node:B_B_node,edge):#对当前X生成Y
    temp_node = copy.deepcopy(X_node)
    
    #在cij、row和Column里删除该行列
    print(edge)
    print("删除前",temp_node.row,temp_node.column)
    C,row,column = dele(temp_node.cij,temp_node.row,temp_node.column,edge)
    print("删除后",row,column)
    temp_node = B_B_node(temp_node.commited,temp_node.ban,C,temp_node.lowbound,row,column)
    
    #消除形成子环的可能
    C = del_sub(temp_node,edge)

    temp_node.commited.append(edge)

    #将temp_cij约化
    h,reduced_cij = reduce(C)
    Y = B_B_node(temp_node.commited,temp_node.ban,reduced_cij,temp_node.lowbound + h,temp_node.row,temp_node.column)
    print("Y下限:",Y.lowbound)
    return Y

def B_B(X_node:B_B_node):
    q = queue.Queue()
    q.put(X_node)
    z = inf
    tour = None
    count = 1
    while not q.empty():
        print("处理第",count,"个节点")
        count += 1
        temp_node = q.get()
        
        if temp_node.n == 2 and temp_node.lowbound <= z:
            z = temp_node.lowbound
            tour = temp_node.commited
            print("z",z)
            print("tour:",tour)
            continue
            
        elif temp_node.lowbound > z:
            print("该节点直接cut,没有分支")
            continue
        else:
            #将所在节点重新计算下界和约化矩阵
            g = 0
            C = copy.deepcopy(c_ij)
            row = [i for i in range(len(C))]
            column = [i for i in range(len(C))]
           
            #已确定边的长度和
            for edge in temp_node.commited:
                g += C[edge[0]][edge[1]]
           
            #删除commited的行和列
            for edge in temp_node.commited:
                C,row,column = dele(C,row,column,edge)
            
            temp_node = B_B_node(temp_node.commited,temp_node.ban,C,0,row,column)

            #消除子环
            print(temp_node.commited)
            temp2 = copy.deepcopy(temp_node)
            for i in range(len(temp_node.commited)):
                temp2.commited = temp_node.commited[:i]
                edge1 = temp_node.commited[i]
                C = del_sub(temp2,edge1)
                temp2.cij = C
            
            #设ban掉的边为inf
            for edge in temp_node.ban:
                C = ban(C,row,column,edge)
            

            h1,C = reduce(C)
            temp_node = B_B_node(temp_node.commited,temp_node.ban,C,g+h1,row,column)
            theta,edge = find_nextedge(temp_node)

            Y_ = build_left(temp_node,theta,edge)
            Y = built_right(temp_node,edge)
            print("Y.n",Y.n)
            print("Y_.n",Y_.n)

            q.put(Y_)
            q.put(Y)
        print("\n")
    return z,tour

x_node = B_B_node([],[],reduce(c_ij)[1],reduce(c_ij)[0],[i for i in range(len(c_ij))],[j for j in range(len(c_ij))])
print(B_B(x_node))